实训四     二叉树的存储与遍历操作                                                         

一、实训目的

1.  掌握二叉树的存储实现。

2. 理解并掌握二叉树的创建与遍历过程。

二、考核办法

必做题部分全做得3分，选做题部分满分2分，至少选一题。

三、实训内容

1.必做内容：（满分3分）

1.建立二叉树的二叉链表表示，实现二叉树的先序、中序和后序遍历。

2.结构体部分代码：
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinTNode,*BinTree;                         /*结点结构体类型*/
函数（a）：
BinTree CreateBinTree()
｛…｝
函数（b）：
void PreOrder(BinTree bt)
｛…｝
函数（c）：
void InOrder(BinTree bt)
｛…｝
函数（d）：
void PostOrder(BinTree bt)
｛…｝                

                                      图1 二叉树
3.要求：（1）完成函数（a），（b），（c），（d）中的递归算法；
（2）编写 main()函数，并调用上述函数，按图1中的二叉树形式建立二叉树。
（3）调用函数（b），（c），（d）将二叉树先序，中序，后序遍历的结果，并输出到屏幕上。
结果如图：

2. 选做内容：（满分2分）

1.用递归的方法打印图1中所有叶子结点并统计叶子结点的个数。

2. 给定一棵用链表表示的二叉树，其根指针为root，试写求二叉树结点的深度的程序。

3.用递归算法编程实现：对二叉树中某一结点，删除以它为根的子树，并释放相应空间。